class Solution(object):
    def subarraysDivByK(self, nums, k):
        prefix = [0] * k
        prefix[0] += 1
        n = len(nums)
        t = 0
        c = 0
        for i in range(n):
            t = (t + nums[i]) % k
            c += prefix[t]
            prefix[t] += 1
        return c


data = Solution()
nums = [4, 5, 0, -2, -3, 1]
k = 5
print(data.subarraysDivByK(nums, k))
